#include <iostream>
#include <vector>
#include "math.h"
#include "math_prime.h"

using namespace std;

// find the next prime number after n
// using the Sieve of Eratosthenes method
int next_prime(int n) {
	int max = 2*n + 1;
	// set all numbers to prime first
	vector<int> prime(max, 1);

	prime[0] = 0;
	prime[1] = 0;

	for (int i = 2; i <= max; i++) {
		if (prime[i]) {
			if (i > n)
				return i;
			// set numbers which are multiple of this number to non-prime
			for (unsigned long int k = i*i; k < max; k += i) {
				prime[k] = 0;
			}
		}
	}
	return -1;
}

int isPrime_simple(int n) {
	for (int i = 2; i < n; i++) {
		if (n%i == 0) {
			return 0;
		}
	}
	return 1;
}

int isPrime_optimized(int n) {
	if (n <= 1)  return 0;
	if (n == 2)  return 1;
	if (n % 2 == 0) 
		return 0;
	int m = (int)sqrt(n*1.0);
    for (int i = 3; i <= m; i+=2) {
		if (n%i == 0) {
			return 0;
		}
	}
	return 1;
}

void test_prime() {
	for (int num = 2; num < 5000; num++)	{
		if (isPrime_optimized(num)) 
			printf("%d, ", num);		
	}
	int current = 980000;
	printf ("\n\nNext prime after %d is %d.\n", current, next_prime(current));
}
